package main

import (
	"errors"
	"fmt"
)

func main() {
	arr := []int{1, 10, 23, 35, 80, 100, 120}
	targets := []int{1, 120, 23, 85}

	for _, target := range targets {

		fmt.Printf("=====【%d】====\n", target)

		idx, err := binarySearch(arr, 0, len(arr), target)
		if err != nil {
			fmt.Println(err)
		} else {
			fmt.Printf("found at index %d\n", idx)
		}

		b := exist(arr, target)
		fmt.Println(b)
	}

}

// [left, right)中查找是否存在数字
func binarySearch(arr []int, left, right int, target int) (int, error) {

	if left >= right {
		return 0, errors.New("not found")
	}

	mid := (left + right) / 2

	if arr[mid] > target {
		return binarySearch(arr, left, mid, target)
	} else if arr[mid] < target {
		return binarySearch(arr, mid+1, right, target)
	} else {
		return mid, nil
	}

}

func exist(arr []int, target int) bool {
	if len(arr) == 0 {
		return false
	}
	// [l, r]区间内查找是否存在该数据
	l, r := 0, len(arr)

	for {
		if l >= r {
			break
		}
		//mid := l + ((r - l) >> 1)
		mid := (l + r) / 2
		if arr[mid] == target {
			fmt.Printf("found 【 %d 】 at index 【 %d 】\n", target, mid)
			return true
		} else if arr[mid] > target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return false

}
